package com.leetcode.weekly.contest.no234th;

import java.util.Arrays;

/**
 * @author 覃国强
 * @date 2021-03-28 10:50
 */
public class A02_还原排列的最少操作步数 {

  public static void main(String[] args) {
    Solution solution = new Solution();
    int permutation = solution.reinitializePermutation(1000);
    System.out.println(permutation);

  }

  static
  class Solution {
    public int reinitializePermutation(int n) {
      if (n == 0) {
        return 0;
      }
      int[] perm = new int[n];
      for (int i = 0; i < n; ++i) {
        perm[i] = i;
      }
      int[] arr = new int[n];
      for (int i = 0; i < n; ++i) {
        if (i % 2 == 0) {
          arr[i] = perm[i / 2];
        } else {
          arr[i] = perm[n / 2 + (i - 1) / 2];
        }
      }

      int[] tmpArr;
      int result = 1;
      while (!arrEquals(perm, arr)) {
        tmpArr = Arrays.copyOf(arr, n);
        ++result;
        for (int i = 0; i < n; ++i) {
          if (i % 2 == 0) {
            arr[i] = tmpArr[i / 2];
          } else {
            arr[i] = tmpArr[n / 2 + (i - 1) / 2];
          }
        }
      }
      return result;
    }

    private boolean arrEquals(int[] perm, int[] arr) {
      for (int i = 0; i < arr.length; ++i) {
        if (perm[i] != arr[i]) {
          return false;
        }
      }
      return true;
    }
  }

}
